<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    串（String） - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						串（String）
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/03/13 10:35 上午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E4%B8%B2%E7%B1%BB%E5%9E%8B%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串类型的定义</h2>
<p>串即是字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表，<strong>记为：</strong> <code>s = 'a1, a2, ......, an</code>(n ≥ 0)</p>
<h3><a id="%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>术语</h3>
<h4><a id="%E4%B8%B2%E9%95%BF" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串长</h4>
<p>串中字符个数(n ≥ 0)，<code>n = 0</code>时称为空串</p>
<h4><a id="%E7%A9%BA%E6%A0%BC%E4%B8%B2" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>空格串</h4>
<p>由一个或多个空格符组成的串</p>
<h4><a id="%E5%AD%90%E4%B8%B2" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>子串</h4>
<p>串<code>s</code>中任意个连续的字符序列叫<code>s</code>的子串，<code>s</code>叫主串</p>
<h4><a id="%E5%AD%97%E7%AC%A6%E4%BD%8D%E7%BD%AE" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>字符位置</h4>
<p>字符在串中的序号</p>
<h4><a id="%E5%AD%90%E4%B8%B2%E4%BD%8D%E7%BD%AE" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>子串位置</h4>
<p>子串的第一个字符在主串的位置</p>
<h4><a id="%E4%B8%B2%E7%9B%B8%E7%AD%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串相等</h4>
<p>串长度相等，且对应位置上的字符相等</p>
<h2><a id="%E4%B8%B2%E7%9A%84%E8%A1%A8%E7%A4%BA%E5%92%8C%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串的表示和实现</h2>
<p>串与线性表的运算有所不同，是以“串的整体”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等</p>
<h3><a id="%E4%B8%B2%E7%9A%84%E4%B8%89%E7%A7%8D%E6%9C%BA%E5%86%85%E8%A1%A8%E7%A4%BA%E6%96%B9%E5%BC%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串的三种机内表示方式</h3>
<h4><a id="%E5%AE%9A%E9%95%BF%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E8%A1%A8%E7%A4%BA%EF%BC%88%E6%95%B0%E7%BB%84%E5%BD%A2%E5%BC%8F%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>定长顺序存储表示（数组形式）</h4>
<p>用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配</p>
<h5><a id="%E4%BE%8B%E5%A6%82" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>例如</h5>
<pre class="line-numbers"><code class="language-c">typedef unsigned char SString[Maxstrlen + 1];
SString s; 
//s的实际容量为256，0位用于存储实际长度，是一个可容纳255个字符的顺序串
</code></pre>
<ul>
<li>定长扩容不便，会存在截断的情况</li>
</ul>
<h4><a id="%E5%A0%86%E5%88%86%E9%85%8D%E5%AD%98%E5%82%A8%E8%A1%A8%E7%A4%BA%EF%BC%88%E9%80%9A%E8%BF%87malloc%E5%87%BD%E6%95%B0%E5%88%86%E9%85%8D%E7%A9%BA%E9%97%B4%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>堆分配存储表示（通过malloc函数分配空间）</h4>
<p>用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得</p>
<pre class="line-numbers"><code class="language-c">typedef struct 
{
    char *ch;
    // 若非空串，按串长分配空间；否则ch = NULL
    int length; //串长度
} HString;
</code></pre>
<h4><a id="%E4%B8%B2%E7%9A%84%E5%9D%97%E9%93%BE%E5%AD%98%E5%82%A8%E8%A1%A8%E7%A4%BA%EF%BC%88%E9%80%9A%E8%BF%87%E9%93%BE%E5%BC%8F%E7%BB%93%E6%9E%84%E5%AD%98%E5%82%A8%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串的块链存储表示（通过链式结构存储）</h4>
<p><img src="media/16471389456317/16471502377721.jpg" alt="" /><br />
<img src="media/16471389456317/16471502500907.jpg" alt="" /></p>
<ul>
<li>存储密度越小，使用越灵活，空间利用率越低</li>
<li>存储密度越大，空间利用率越高，使用越不 灵活</li>
</ul>
<h2><a id="%E4%B8%B2%E7%9A%84%E6%A8%A1%E5%BC%8F%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>串的模式匹配算法</h2>
<p>模式匹配（Pattern Matching），即子串定位运算（Index函数），求子串在主串中第一次出现的位置，即如何实现Index(S, T, pos)函数，S称为被匹配的串，T称为模式串</p>
<p>若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0，若S包含串T，则称“匹配成功”，否则称“匹配不成功”</p>
<h3><a id="%E7%AE%97%E6%B3%95%E5%88%86%E9%85%8D" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>算法分配</h3>
<h4><a id="bf%E7%AE%97%E6%B3%95%EF%BC%88%E5%8F%88%E7%A7%B0%E5%8F%A4%E5%85%B8%E6%88%96%E7%BB%8F%E5%85%B8%E7%9A%84%E3%80%81%E6%9C%B4%E7%B4%A0%E7%9A%84%E3%80%81%E7%A9%B7%E4%B8%BE%E7%9A%84%E6%96%B9%E6%B3%95%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>BF算法（又称古典或经典的、朴素的、穷举的方法）</h4>
<p>从被匹配串的第一位开始匹配，如果第一位相同，则开始匹配第二位，若不相同，则回溯到被匹配串的下一首位重新开始匹配，以此类推</p>
<ul>
<li>若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为<code>O(n * m)</code></li>
<li>但一般情况下BF算法的时间复杂度为<code>O(n + m)</code></li>
</ul>
<h4><a id="kmp%E7%AE%97%E6%B3%95%EF%BC%88%E9%80%9F%E5%BA%A6%E5%BF%AB%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>KMP算法（速度快）</h4>
<p>KMP算法时间复杂度为<code>O(n + m)</code>，其改进在于，每当一趟匹配过程中出现字符比较不相等时，不需要回溯指针，而是理由已经部分匹配的结果将模式向右滑动尽可能远的一段距离，继续进行比较</p>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  














<script src="asset/prism.js"></script>









</body>

</html>